#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		vector<vector<int> > result;
		if((n<0) || (k<0))
			return result;

		vector<int> r(k,0);
		for(int i=1;i<=k;i++)
			r[i-1] = i;

		result.push_back(r);

		while(next_comb(r,n))
			result.push_back(r);
		return result;
    }

private:
	bool next_comb(vector<int>& r,int n){		
		int k = r.size();
		for(int i = r.size()-1;i>=0;i--){
			if(r[i] < (n-k+i+1)){
				r[i]++;
				for(int j=i+1;j<k;j++)
					r[j] = r[i]+j-i;
				return true;
			}
		}
		return false;
	}
};
#endif